1. Field of the Invention
The invention relates to solution of problems of the class equivalent to optimal allocation determination in a combinatorial auction.
2. Background
In sequential auctions, the items are auctioned one at a time. If an agent has preferences over bundles (combinations of items), then bidding in such auctions is difficult. To determine one's valuation for an item, one needs to guess what items one will receive in later auctions. This requires speculation of what the others will bid in the future. This introduces uncertainty and computational cost, both of which reduce the efficiency. Furthermore, in auctions with a reasonable number of items, the lookahead becomes intractable, and there is no easy way to bid rationally. Therefore, the future uncertainties of sequential auctions result in inefficiencies making it difficult for rational agents to bid.
An alternative to sequential auctioning of the interdependent items would be to open them all for auction in parallel. However, some of the same problems prevail. For example, when bidding for an item, the bidder does not know its valuation because it depends on which other items the bidder wins, which in turn depends on how others will bid (in sealed-bid auctions this is not known to the bidder, and in open-cry auctions it may become known only later). In parallel auctions, an additional difficulty arises: each bidder would like to wait until the end to see what the going prices will be. If each bidder plans to wait until the end, bidding will not commence. Therefore, parallel auctions also have future uncertainties that result in inefficiencies.
One solution to this problem is to allow the bidders to place bids for combinations of items instead of only on individual items. This is an auction protocol known as a "combinatorial auction". Determining the winning bids in a combinatorial auction, however, in a way that maximizes the auctioneer's revenue is intractable (NP-complete).
There are situations involving the exchange of items for value in which there may exist synergies in the preferences for combinations of the items. A common situation in which this is found is in a combinatorial auction. In this situation an auctioneer holding properties wishes to maximize the value obtained through the auction of the properties. Bidders may have a willingness to exchange more value for combinations of properties than they would for individual elements of the combination, if considered alone and aggregated. For example, if A, B, C, D, and E were adjacent parcels of land along the bank of a river, and a bidder had a willingness to pay for parcel A alone, say P1; for parcel B, alone, say P2; and for parcel C alone, say P3, the bidder may have a greater willingness to pay for the combination of the three adjacent parcels {A, B, C} than P1+P2+P3. This synergistic or superadditive effect may be bidder-specific. This effect may also be present in a reverse auction context where buyers are the auctioneers, for example, where portions of a construction contract are offered to be bid upon by construction contractors.
To the auctioneer, it is then desirable, to structure an auction to allow bidder to bid in combinations to gain the value of their synergies. Similarly, it is desirable for bidders to be able to bid on combinations. A bidder may be unwilling to bid more than the sum of his or her willingnesses to pay for individual properties and thus have to forgo the opportunity to reap the synergistic gains. Alternatively, a bidder may be exposed to risk by overbidding in an eventually unsuccessful attempt to obtain a combination of properties.
Conventionally, practical implementations of the class of situations involving superadditive preferences, for example a combinatorial auction, have proven difficult because of the complexity of considering numerous possible combinations of bids for items. Given the complexity of the calculations, a computer or equivalent device is a virtual necessity to perform the task. Conventionally, computer-implemented methods of selecting winning bids in a combinatorial auction involve representing the items and bids in a computer or equivalent and performing particular operations on this data to determine winning bids. However, conventional methods are impractical for many applications.
Winner determination in combinatorial auctions means choosing which bids to accept so as to maximize the sum of the prices of the accepted bids (under the constraint that each item can be given out only once, i.e. bids that overlap in items cannot be accepted together). This is the same problem as the abstract combinatorial problem called weighted set packing. The fact that weighted set packing is NP-complete means that there is no polynomial time (in the number of bids placed) algorithm for finding a revenue maximizing allocation in combinatorial auctions--unless the complexity class NP equals the complexity class P which is extremely unlikely. Generally, the number of possible allocation is O(#item (#items) and .omega.(#item (#items/2)), so exhaustive search is impractical unless the number of auctioned items is very small (less than about 15 using conventional techniques).
One conventional approach to optimal winner determination involves dynamic programming. However, this method requires .OMEGA.(2 #items ) and O(2 (2#items)) operations independent of the numbers of the bids that have actually been placed. This method does not capitalize on the common situation that, in fact, most combinations will not have bids placed on them. This means that the algorithm will not scale well past about 20-30 items even if very few bids have been placed.
Another conventional approach is to compromise optimality of the solution. Such approaches try to construct algorithms that run in polynomial time in the number of bids, and guarantee that the solution is within a bound from optimal. However, there is a strong recent inapproximability result by H.ang.astad that guarantees that no polynomial time algorithm can guarantee that the solution is within a bound of #bids (1-.epsilon.) or better for any .epsilon.&gt;0-(unless NP=probabilistic P which is very unlikely). Other conventional approaches try to devise polynomial time approximation schemes for special cases, but in these approaches, the solution quality guarantees are so weak as to be impractical in the auction application.
Yet another conventional approach is to place severe restrictions on which combinations may be bid upon. However, such restrictions can lead to inefficient outcomes because the bidders are faced with similar uncertainties as in bidding for interrelated items individually.
Thus it would be desirable to have a method and apparatus for optimal winner determination in combinatorial auction-type problems that does not require exponential time or memory; can capitalize on the fact that most combinations will not have bids placed on them in practice; does not compromise on the optimality of the solution; is not limited to special cases; and does not place restrictions on what combinations may be bid upon. It would be further desirable to have such a method that could operate as an anytime algorithm.